#双链表
class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        self.pre=None

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(0)
        self.size=0

    def head_insert(self,data):#头插法
        new_node = Node(data)
        new_node.next=self.head.next
        new_node.pre=self.head
        if self.head.next:
            self.head.next.pre=new_node
        self.head.next=new_node
        self.size+=1

    def tail_insert(self,data):#尾插法
        new_node = Node(data)
        current = self.head
        while current.next:
            current = current.next
        new_node.next = current.next
        new_node.pre = current
        current.next = new_node
        self.size+=1

    def delete_node(self,data):#删除
        current = self.head.next
        while current:
            if current.data==data:
                current.pre.next=current.next
                if current.next:
                    current.next.pre=current.pre
                self.size-=1
                del current
                return True
            current = current.next
        return False

    def print_list(self):#遍历
        current=self.head.next
        while current:
            print(current.data)
            current=current.next

if __name__=='__main__':
    dll=DoublyLinkedList()
    dll.head_insert(2)
    dll.head_insert(1)
    dll.tail_insert(3)
    dll.tail_insert(4)
    dll.delete_node(1)
    dll.print_list()

